package likou

func exist(board [][]byte, word string) bool {
	wordByte := []byte(word)
	wordLen := len(wordByte)
	m, n := len(board), len(board[0])
	// 规定移动动作： 上下左右
	dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	var dfs func(int, int, int) bool

	dfs = func(index int, x, y int) bool {
		// 结束条件，判断当前节点
		if board[x][y] != wordByte[index] {
			return false
		} else if index == wordLen - 1 {
			return true
		}

		//  记录旧值，后面恢复用
		oldword := board[x][y]
		board[x][y] = '0'
		for _, dir := range dirs{
			// 计算下一节点的坐标
			nextRow := x + dir[0]
			nextCol := y + dir[1]
			if nextRow >= 0 && nextRow < m &&
				nextCol >= 0 && nextCol < n &&
				board[nextRow][nextCol] != '0'{
				if dfs(index + 1, nextRow, nextCol) {
					return true
				}
			}
		}
		// 回溯，撤销
		board[x][y] = oldword

		return false
	}

	for row := 0; row < m; row++ {
		for col := 0; col < n; col++ {
			if board[row][col] == word[0] {
				if dfs(0, row, col) {
					return true
				}
			}
		}
	}
	return false
}

